#include<iostream>
using namespace std;
int oneSort(int a[],int x,int y); 
void qSort(int a[],int,int);   
int main(){
    int a[]={1,3,5,7,9,2,4,6,8};
    int n=sizeof(a)/sizeof(int);
    qSort(a,0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}
int oneSort(int a[],int x,int y){
    int i=x; 
    int j=y;  
    int tmp=a[x];   
    while(i<j){  
        while(tmp<a[j]&&i<j) 
               j--;
        if(i<j){    
            a[i]=a[j];  
            i++;
        }
        while(a[i]<tmp&&i<j) 
            i++;
        if(i<j){
            a[j]=a[i];  
                        
            j--;
        }
    }
    a[i]=tmp; 
                
                
    return i; 
}
void qSort(int a[],int x,int y){
    if(x<y){
        int k=oneSort(a,x,y); 
                        
        qSort(a,x,k-1);
        qSort(a,k+1,y);
    }
}


